NIC 20783
						    Part of NIC 20414

	    STANFORD ARTIFICIAL INTELLIGENCE LABORATORY
		    1973 ARPA Project Summary

Prepared for:	ARPA IPT Principal Investigators Conference
		Los Angeles, Feb 6-8, 1974

Prepared by:	John McCarthy
		Computer Science Department
		Stanford University
		Stanford, California 94305

HAND-EYE RESEARCH

During 1973,  the  hand-eye group assembled an automobile  water pump
using  the arm, tools,   touch, force sensing  and vision.  The first
version of an  arm control language was  implemented, the second  arm
was finished, and tool changing accomplished.

The  semantics-based region  analyzer  was  a breakthrough  in  scene
segmentation.   Description  of complex  objects has  progressed from
describing parts of objects to complete descriptions of dolls,  tools
and toy  horses, and  matching of  objects for  recognition is  at an
advanced  stage.    Model driven  perception  of  outdoor  scenes and
cardiac angiograms has been implemented in Yakimovsky's  thesis,  and
the  use   of  models  for   perception  of  polyhedral   scenes  was
accomplished in Grape's thesis.

Region growing techniques have been developed for medium-angle stereo
images  of outdoor scenes  to grow  regions of constant  depth (hence
constant parallax) using correlation measures to determine  whether a
point  belongs  to  the  region.  These  techniques  will  facilitate
three-dimensional modelling of the scene.

NATURAL LANGUAGE UNDERSTANDING

Yorick Wilks  and Annette Herskovits  have developed  an experimental
translation  system,    working  from  English  to French,  based  on
semantic parsing  of  source  statements.   It  is now  able  to  use
unquantified,  fuzzy-matched,  pattern (or frame) rules  to resolve a
range of  difficult pronoun identifications in small texts in more or
less unrestricted English.

SPEECH RECOGNITION

We have been working on a fast pitch  period detector and an improved
formant  tracker which  does better than  most formant  trackers even
when no tracking  is done. Three  papers summarizing recent  progress
have been submitted for the April IEEE meeting on Speech.

MATHEMATICAL THEORY OF COMPUTATION

Using LCF  (an interactive proof  checker), an axiomatization  of the
natural numbers,  integers, finite sets and  lists was recently made.
From these a collection of about 900 theorems were proved.  These now
form an available data base of theorems.

The semantics of  LISP was made within the LCF  framework and many of
the common properties of  some LISP functions were  proved.  A  major
accomplishment in this area  was to give a partial  correctness proof
for  the LISP interpreter given  in the LISP  1.5 programming manual.
This  proof  required  several  thousand  steps.    A  proof  of  the
correctness of a LISP compiler was also started.

There is a new  system designed specifically for the  verification of
programs  in PASCAL.   It has been  used to prove  the correctness of
many standard  sorting programs,   pattern  matching  programs and  a
simple compiler.   Its rule dictionary  has been extended so  that it
can be  used to verify programs involving coroutines and simple kinds
of parallel processes.  A  version of this  system for  PL1 has  been
constructed  recently.  The  system is  currently being used  both at
Stanford-AI and at USC-ISI.

We produced  the first  version of FOL,   a  first order logic  proof
checker.  Several  proofs have been generated using FOL and different
axiomatizations in an attempt to compare the effect of  the different
axiomatizations.     One  such   problem  has  been   the  "mutilated
checkerboard" problem.

REPRESENTATION THEORY

Work  continued on  how  to  represent  information about  the  world
sufficient to determine  that an action strategy will achieve a goal.
Improved treatments were  found for describing  events that occur  in
parallel.   Improvements were  also made in  expressing the  facts in
first order logic with set theory using the FOL proof checker.

PROGRAM  GENERATION

An automatic  programming system has  been developed that  accepts as
input  an environment  of  programming methods  and a  problem  to be
solved.   It  applies  heuristic  problem-solving methods,    and  if
successful,  outputs  a program for solving the problem.   The output
programs  are  in  an  ALGOL-like  language  containing  assignments,
function calls,  while loops, conditional branches, and non-recursive
procedure calls.   This system  has been tested  on everyday planning
problems and computing arithmetical functions.  Recently it has  been
used to  generate procedures for  the assembly  and repair of  simple
machinery.

PROGRAM UNDERSTANDING SYSTEMS

Our work on program understanding systems has focused on: (1)  better
methods  of program  specification;  (2) codification  of programming
knowledge; and (3) implementation  of program understanding  systems.
The programming area  selected for study is  list processing. Several
"human-oriented"  methods of program specification are being studied,
for example input-output pairs  of lists,  elipsis notation  (to mean
"and so on"), and some some limited natural language.

Several program-writing  systems have  been built  and studied.   The
most   successful  has  produced  over   twenty  list  transformation
programs, ranging from a  simple "reverse" program to fairly  complex
combination, permutation, and subset  transformation programs.

LANGUAGE DESIGN

SAIL (an extended dialect  of ALGOL 60) has been  further extended to
include a  flexible multi-process facility, coroutines, backtracking,
and related  constructs.   The  new version  and  a new  manual  were
distributed  to a  dozen  or  so installations  (mostly  in the  ARPA
community) that use SAIL regularly.

PUB  is  a  document  compiler   that  automatically  handles  cross-
references  to pages,   sections,   equations,   or  whatever.   As a
byproduct, it creates a table of  contents and sorted index.  It  has
recently been extended to produce multi-font output on the XGP (Xerox
Graphics  Printer) and has become the standard documentation language
here,     at  Carnegie-Mellon  University,   and  at  several   other
installations that now have XGPs.

PROCESSOR DESIGN

We completed the design  of a novel central processor  early in 1973.
It was  a 36 bit machine capable  of executing PDP-10 instructions at
three to four times the speed of a KI-10 CPU.  The design  featured a
2K  word  cache memory,  user-accessible  microcode,  and a  "console
computer"  (PDP-11 class, with attached keyboard  and CRT) to monitor
and debug the big machine.

The processor was not fabricated.  Nevertheless, it was successful in
influencing  commercial  development  efforts  that  we  expect  will
substantially benefit  the ARPA  community and  timesharing users  in
general.

In  support of  the  processor  design  activity,   we  developed  an
interactive  design system  for digital  logic.   This  collection of
programs makes it possible to define and interconnect logic elements,
lay out printed circuit cards, wire-wrap cards, and backpanels and to
automatically  produce the required artwork,   wiring commands,  etc.
The  system  provides automatic  checking  of  wiring  rules  and  of
consistency between alternate  representations. It also automatically
generates test procedures and programs for checking individual  logic
cards.   This system is  now being used  in the MIT  A.I. Laboratory,
Carnegie-Mellon University, and Digital Equipment Corporation.

NEWS SERVICE

The news storage  and retrieval system  APE permits an  individual to
read  selectively  the   news  from  a  national  wire  service  (the
Associated Press)  and to  be  notified when  a story  of  particular
interest comes in.   Selection of stories is done  through the use of
keywords and combinations of keywords which the user specifies.